#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""
https://www.geeksforgeeks.org/shortest-un-ordered-subarray/


单调栈解法:
        1. 第一遍:  从左到右单调递增栈:

        2. 第二遍: 从右到左, 单调递减栈:
"""

class Solution:
    def __init__(self):
        pass

    def shortest_unordered_subarray(self, nums):
        self.stack = []

        return self.find_left_unordered(nums), self.find_right_unordered(nums)

    def find_left_unordered(self, nums):
        self.stack.clear()
        min_left = len(nums)
        for i,e in enumerate(nums):
            while self.stack:
                top_idx = self.stack[-1]
                if e < nums[top_idx]:
                    min_left = min(min_left, top_idx)
                    self.stack.pop()
                else:
                    # e >= nums[top_idx]
                    break

            self.stack.append(i)

        return min_left

    def find_right_unordered(self, nums):
        self.stack.clear()
        max_right = -1
        for i in range(len(nums)-1, -1, -1):
            e = nums[i]

            while self.stack:
                top_idx = self.stack[-1]
                if e > nums[top_idx]:
                    max_right = max(max_right, top_idx)
                    self.stack.pop()
                else:
                    # e >= nums[top_idx]
                    break

            self.stack.append(i)

        return max_right

    def reverse_range(self, num):
        return range(num-1, -1, -1)



def test():
    s = Solution()
    # nums = [7, 9, 10, 8, 11]
    nums = [1, 3, 6, 5, 4, 9]

    left_idx, right_idx = s.shortest_unordered_subarray(nums)
    print(left_idx, right_idx, right_idx-left_idx+1)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
